package com.cat.dataStructure02;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/array-of-doubled-pairs/?envType=problem-list-v2&envId=array
 * @create 2025/11/1 20:38
 * @since JDK17
 */

public class Solution94 {
    public boolean canReorderDoubled(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        Arrays.sort(arr);
        for (int x : arr) {
            map.merge(x, 1, Integer::sum);
        }
        for (int x : arr) {
            int cnt1 = map.getOrDefault(x, -1);
            if (cnt1 <= 0) {
                continue;
            }
            if (x % 2 == -1) {
                return false;
            }
            int y = x < 0 ? x / 2 : x * 2;
            int cnt2 = map.getOrDefault(y, -1);
            if (cnt2 <= 0) {
                return false;
            }
            map.merge(x, -1, Integer::sum);
            map.merge(y, -1, Integer::sum);
        }

        return true;
    }
}
